import java.util.Arrays;

public class Test {

    /*
     * 有效的三角形个数
     * 注意：任意两条边长之和大于第三边，则是有效三角形(N^3)
     * 优化：较小的两条边之和大于最大边
     * */

    public static void main(String[] args) {
        int[] nums = {2,2,3,4};
        System.out.println(triangleNumber(nums));
    }

    //利用单调性，使用双指针算法来解决问题
    public static int triangleNumber(int[] nums) {
        //1.优化：排序
        Arrays.sort(nums);

        //2.利用双指针解决问题
        int ret = 0;
        int n = nums.length;
        for (int i = n - 1; i >= 2 ; i--) {//先固定最大的数
            //利用双指针快速找出符合要求的三元组的个数
            int left = 0;
            int right = i - 1;
            while(left < right){
                if(nums[left] + nums[right] > nums[i]){
                    ret += right - left;
                    right--;
                }else{
                    left++;
                }
            }
        }
        return ret;
    }


}
